package dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wcj
 * @Date 2021/7/6 19:53
 * @Version 1.0
 */
public class PathSumSecond {

    private static List<List<Integer>> res;
    private static LinkedList<Integer> path;
    private static int target;

    /**
     * 找出所有从根节点到叶子节点且权值和为target的路径
     * 深搜：
     * ①递归方法的设计：dfs(TreeNode root,int target)同前一个题
     * ②递归出口：同前一个
     * ③递归组合方式
     *
     * @return
     */
    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new ArrayList<>();
        path = new LinkedList<>();
        target = sum;
        dfs(root, target);
        return res;
    }

    public static void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null && sum == root.val) {
            path.add(root.val);
            res.add(new ArrayList<>(path));
            path.removeLast();
            return;
        }
        path.add(root.val);
        dfs(root.left, sum - root.val);
        dfs(root.right, sum - root.val);
        path.removeLast();
    }
}
